package com.xsjiong.hoofen;

import android.support.annotation.NonNull;
import android.support.annotation.Nullable;

public class SparseArrayPlus<E> implements Cloneable {
	private static final long[] EMPTY_LONGS = new long[0];
	private static final Object[] EMPTY_OBJECTS = new Object[0];

	private static final Object DELETED = new Object();
	private boolean mGarbage;
	private long[] mKeys;
	private E[] mValues;
	private int mSize;

	public SparseArrayPlus() {
		this(10);
	}

	private static int idealIntArraySize(int need) {
		return idealByteArraySize(need * 4) / 4;
	}

	private static int idealByteArraySize(int need) {
		for (int i = 4; i < 32; ++i) {
			if (need <= (1 << i) - 12) {
				return (1 << i) - 12;
			}
		}

		return need;
	}

	public SparseArrayPlus(int initialCapacity) {
		this.mGarbage = false;
		if (initialCapacity == 0) {
			this.mKeys = EMPTY_LONGS;
			this.mValues = (E[]) EMPTY_OBJECTS;
		} else {
			initialCapacity = idealIntArraySize(initialCapacity);
			this.mKeys = new long[initialCapacity];
			this.mValues = (E[]) new Object[initialCapacity];
		}

		this.mSize = 0;
	}

	@Nullable
	public E get(long key) {
		return this.get(key, null);
	}

	public E get(long key, E valueIfKeyNotFound) {
		int i = binarySearch(this.mKeys, this.mSize, key);
		return i >= 0 && this.mValues[i] != DELETED ? this.mValues[i] : valueIfKeyNotFound;
	}

	private static int binarySearch(long[] array, int size, long value) {
		int lo = 0;
		int hi = size - 1;

		while (lo <= hi) {
			int mid = lo + hi >>> 1;
			long midVal = array[mid];
			if (midVal < value) {
				lo = mid + 1;
			} else {
				if (midVal <= value) {
					return mid;
				}

				hi = mid - 1;
			}
		}

		return ~lo;
	}

	public void delete(int key) {
		int i = binarySearch(this.mKeys, this.mSize, key);
		if (i >= 0 && this.mValues[i] != DELETED) {
			this.mValues[i] = (E) DELETED;
			this.mGarbage = true;
		}

	}

	public void remove(int key) {
		this.delete(key);
	}

	public void removeAt(int index) {
		if (this.mValues[index] != DELETED) {
			this.mValues[index] = (E) DELETED;
			this.mGarbage = true;
		}

	}

	public void removeAtRange(int index, int size) {
		int end = Math.min(this.mSize, index + size);

		for (int i = index; i < end; ++i) {
			this.removeAt(i);
		}

	}

	private void gc() {
		int n = this.mSize;
		int o = 0;
		long[] keys = this.mKeys;
		Object[] values = this.mValues;

		for (int i = 0; i < n; ++i) {
			Object val = values[i];
			if (val != DELETED) {
				if (i != o) {
					keys[o] = keys[i];
					values[o] = val;
					values[i] = null;
				}

				++o;
			}
		}

		this.mGarbage = false;
		this.mSize = o;
	}

	public void put(long key, E value) {
		int i = binarySearch(this.mKeys, this.mSize, key);
		if (i >= 0) {
			this.mValues[i] = value;
		} else {
			i = ~i;
			if (i < this.mSize && this.mValues[i] == DELETED) {
				this.mKeys[i] = key;
				this.mValues[i] = value;
				return;
			}

			if (this.mGarbage && this.mSize >= this.mKeys.length) {
				this.gc();
				i = ~binarySearch(this.mKeys, this.mSize, key);
			}

			if (this.mSize >= this.mKeys.length) {
				int n = idealIntArraySize(this.mSize + 1);
				long[] nkeys = new long[n];
				Object[] nvalues = new Object[n];
				System.arraycopy(this.mKeys, 0, nkeys, 0, this.mKeys.length);
				System.arraycopy(this.mValues, 0, nvalues, 0, this.mValues.length);
				this.mKeys = nkeys;
				this.mValues = (E[]) nvalues;
			}

			if (this.mSize - i != 0) {
				System.arraycopy(this.mKeys, i, this.mKeys, i + 1, this.mSize - i);
				System.arraycopy(this.mValues, i, this.mValues, i + 1, this.mSize - i);
			}

			this.mKeys[i] = key;
			this.mValues[i] = value;
			++this.mSize;
		}

	}

	public void putAll(@NonNull android.support.v4.util.SparseArrayCompat<? extends E> other) {
		int i = 0;

		for (int size = other.size(); i < size; ++i) {
			this.put(other.keyAt(i), other.valueAt(i));
		}

	}

	public int size() {
		if (this.mGarbage) {
			this.gc();
		}

		return this.mSize;
	}

	public boolean isEmpty() {
		return this.size() == 0;
	}

	public long keyAt(int index) {
		if (this.mGarbage) {
			this.gc();
		}

		return this.mKeys[index];
	}

	public E valueAt(int index) {
		if (this.mGarbage) {
			this.gc();
		}

		return this.mValues[index];
	}

	public void setValueAt(int index, E value) {
		if (this.mGarbage) {
			this.gc();
		}

		this.mValues[index] = value;
	}

	public int indexOfKey(long key) {
		if (this.mGarbage) {
			this.gc();
		}

		return binarySearch(this.mKeys, this.mSize, key);
	}

	public int indexOfValue(E value) {
		if (this.mGarbage) {
			this.gc();
		}

		for (int i = 0; i < this.mSize; ++i) {
			if (this.mValues[i] == value) {
				return i;
			}
		}

		return -1;
	}

	public boolean containsKey(int key) {
		return this.indexOfKey(key) >= 0;
	}

	public boolean containsValue(E value) {
		return this.indexOfValue(value) >= 0;
	}

	public void clear() {
		int n = this.mSize;
		Object[] values = this.mValues;

		for (int i = 0; i < n; ++i) {
			values[i] = null;
		}

		this.mSize = 0;
		this.mGarbage = false;
	}

	public void append(long key, E value) {
		if (this.mSize != 0 && key <= this.mKeys[this.mSize - 1]) {
			this.put(key, value);
		} else {
			if (this.mGarbage && this.mSize >= this.mKeys.length) {
				this.gc();
			}

			int pos = this.mSize;
			if (pos >= this.mKeys.length) {
				int n = idealIntArraySize(pos + 1);
				long[] nkeys = new long[n];
				Object[] nvalues = new Object[n];
				System.arraycopy(this.mKeys, 0, nkeys, 0, this.mKeys.length);
				System.arraycopy(this.mValues, 0, nvalues, 0, this.mValues.length);
				this.mKeys = nkeys;
				this.mValues = (E[]) nvalues;
			}

			this.mKeys[pos] = key;
			this.mValues[pos] = value;
			this.mSize = pos + 1;
		}
	}

	public String toString() {
		if (this.size() <= 0) {
			return "{}";
		} else {
			StringBuilder buffer = new StringBuilder(this.mSize * 28);
			buffer.append('{');

			for (int i = 0; i < this.mSize; ++i) {
				if (i > 0) {
					buffer.append(", ");
				}

				long key = this.keyAt(i);
				buffer.append(key);
				buffer.append('=');
				Object value = this.valueAt(i);
				if (value != this) {
					buffer.append(value);
				} else {
					buffer.append("(this Map)");
				}
			}

			buffer.append('}');
			return buffer.toString();
		}
	}
}